//一条包含字母 A-Z 的消息通过以下映射进行了 编码 ： 
//
// 
//'A' -> "1"
//'B' -> "2"
//...
//'Z' -> "26" 
//
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为： 
//
// 
// "AAJF" ，将消息分组为 (1 1 10 6) 
// "KJF" ，将消息分组为 (11 10 6) 
// 
//
// 注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。 
//
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。 
//
// 题目数据保证答案肯定是一个 32 位 的整数。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "12"
//输出：2
//解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
// 
//
// 示例 2： 
//
// 
//输入：s = "226"
//输出：3
//解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
// 
//
// 示例 3： 
//
// 
//输入：s = "0"
//输出：0
//解释：没有字符映射到以 0 开头的数字。
//含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
//由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 100 
// s 只包含数字，并且可能包含前导零。 
// 
// Related Topics 字符串 动态规划 👍 1217 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.*;

/**
 * [P91]_解码方法
 *
 * @author cjl
 * @date 2022-07-30 16:45:57
 */
public class P91_DecodeWays {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P91_DecodeWays().new Solution();
    }

    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        Set<String> keySet = new HashSet() {
            {
                add("1");
                add("2");
                add("3");
                add("4");
                add("5");
                add("6");
                add("7");
                add("8");
                add("9");
                add("10");
                add("11");
                add("12");
                add("13");
                add("14");
                add("15");
                add("16");
                add("17");
                add("18");
                add("19");
                add("20");
                add("21");
                add("22");
                add("23");
                add("24");
                add("25");
                add("26");
            }
        };

        /**
         * 解法二：f(i) = f(i-1) &&(i>0, s(i-1) !='0') + f(i-2) && (i>1, s(i-2) != '0' , s(i-2) * 10 +s(i-1) <= 26)
         * f(i)表示前i个元素编码数；
         * @param s
         * @return
         */
        public int numDecodings(String s) {
           int[] fn = new int[s.length() +1];
           fn[0] = 1;  // 表示不使用元素时有解，fn// [1] = fn[0]=1
            for(int i = 1; i <= s.length() ;i ++){
                //s.charAt(i-1) 表示第i-1
                if(s.charAt(i-1) != '0'){
                    fn[i] += fn[i-1];
                }
                if(i>1 && s.charAt(i-2) != '0' && (s.charAt(i-2) -'0') * 10 + (s.charAt(i-1) - '0') <= 26){
                    fn[i] += fn[i-2];
                }
            }
            return fn[s.length()];
        }

//        public int numDecodings(String s) {
//            List<List<String>> resList = new ArrayList<>();
//            List<String> currList = new ArrayList<>();
//            decodedingRolling(s, currList, 0, resList);
//            return resList.size();
//        }

        /**
         * 解法一：回溯法
         *
         * @param s
         * @param currList
         * @param n
         * @param resList
         */
        public void decodedingRolling(String s, List<String> currList, int n, List<List<String>> resList) {
            if (n == s.length()) {
                resList.add(new ArrayList<>(currList));
            }
            if (n + 1 <= s.length() && keySet.contains(s.substring(n, n + 1))) {
                currList.add(s.substring(n, n + 1));
                decodedingRolling(s, currList, n + 1, resList);
                currList.remove(currList.size() - 1);
            }
            if (n + 2 <= s.length() && keySet.contains((s.substring(n, n + 2)))) {
                currList.add(s.substring(n, n + 2));
                decodedingRolling(s, currList, n + 2, resList);
                currList.remove(currList.size() - 1);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}